home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_08 / qc.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-07  |  11.8 KB  |  449 lines
  1. ///////////////////////////////////////////////////////
  2. //  Listing 2 - QC.CPP: Quadcode support routines
  3. //  Written by:
  4. //    Kenneth Van Camp
  5. //    RR #1 Box 1255
  6. //    East Stroudsburg, PA  18301
  7. //    (717)223-8620
  8. //
  9. //  Functions -
  10. //    QuadCode::FreeMem         free memory from qc
  11. //    QuadCode::QuadCode        constructor from (I,J)
  12. //    QuadCode::Init            initializer from string
  13. //    QuadCode::GetQuit         get val of single quit
  14. //    QuadCode::SetQuit         set val of single quit
  15. //    QuadCode::ToIJ            convert to (I,J) coords
  16. //    QuadCode::Compare         compare two quadcodes
  17. //    QuadCode::Sibling         are two qc's siblings?
  18. //    QuadCode::Contains        does qc contain it?
  19. //    QuadCode::MakeParent      make qc into its parent
  20. //    QuadCode::operator=       assignment operator
  21. //    operator<<                qc "put to" stream
  22. //    operator>>                qc "get from" stream
  23. //
  24. ///////////////////////////////////////////////////////
  25.  
  26. #include <stdio.h>
  27. #include <stdlib.h>
  28. #include <string.h>
  29. #include <assert.h>
  30. #ifdef __TURBOC__
  31. #include <iostream.h>
  32. #else
  33. #include <stream.hpp>
  34. #endif
  35. #include "qc.h"
  36.   
  37. // The following macro returns the number of bytes reqd
  38. // to store a quadcode, given the number of quits:
  39. #define QC_NBYTES(q)    (((q) - 1) / 4 + 1)
  40.  
  41. // These are shifts & masks to extract a single quit
  42. static int  QCshifts[4] = { 6, 4, 2, 0 };
  43. static int  QCmasks[4]  = { 3<<6, 3<<4, 3<<2, 3 };
  44. // This is the inverse mask:
  45. static int  QCimasks[4] =
  46.     { 0xff^(3<<6), 0xff^(3<<4), 0xff^(3<<2), 0xff^3 };
  47. // And these are masks for each bit in a normal byte:
  48. static int  bitmasks[8] =
  49.     { 1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7 };
  50.  
  51. ///////////////////////////////////////////////////////
  52. // QuadCode::FreeMem: Free dynamic memory.
  53.  
  54. #ifndef STAT_QC
  55. void QuadCode::FreeMem (void)
  56. {
  57.   if (nquits > 0 && qca)
  58.     delete qca;
  59.   qca = NULL;
  60.   nquits = 0;
  61. } // QuadCode::FreeMem
  62. #endif // STAT_QC
  63.  
  64. ///////////////////////////////////////////////////////
  65. // QuadCode::QuadCode: QuadCode constructor from (I,J)
  66. // coordinates of the upper-left corner of the qc.
  67.  
  68. QuadCode::QuadCode (COORD i, COORD j, int nq)
  69. // i      is the vertical row# of quadcode (0 at top)
  70. // j      is the horizontal column# of quadcode
  71. // nq     is the # of quits in quadcode
  72. {
  73. #ifndef STAT_QC
  74.   qca = NULL;
  75. #endif
  76.   nquits = 0;
  77.   assert (nq > 0 && nq <= MAXQUITS);
  78.  
  79.   // We traverse both the (i,j) coordinates and the qc
  80.   // from the msb to the lsb and msq to msq.  Note the
  81.   // following assumes MAXQUITS is a multiple of 8.
  82. #ifdef MSB_FIRST
  83.   BYTE *ip = (BYTE *)&i + (MAXQUITS - nq) / 8;
  84.   BYTE *jp = (BYTE *)&j + (MAXQUITS - nq) / 8;
  85. #else
  86.   BYTE *ip = (BYTE *)&i + sizeof(COORD) - 1 -
  87.       (MAXQUITS - nq) / 8;
  88.   BYTE *jp = (BYTE *)&j + sizeof(COORD) - 1 -
  89.       (MAXQUITS - nq) / 8;
  90. #endif
  91.  
  92.   int bit = 7 - (MAXQUITS - nq) % 8;
  93.   int nbytes = QC_NBYTES (nq);
  94. #ifndef STAT_QC
  95.   qca = new BYTE [nbytes];
  96.   assert (qca != NULL);
  97. #endif
  98.  
  99.   memset (qca, '\0', nbytes);
  100.   BYTE  *p = qca;
  101.   nquits = nq;
  102.  
  103.   int   pos = 0;        // position within qc (0,1,2,3)
  104.   for ( ; nq > 0; nq--)
  105.   {
  106.     if (*ip & bitmasks[bit])
  107.       *p |= 1 << (QCshifts[pos] + 1);
  108.     if (*jp & bitmasks[bit])
  109.       *p |= 1 << QCshifts[pos];
  110.     // Advance to next quit
  111.     if (++pos > 3)
  112.     {
  113.       pos = 0;
  114.       p++;
  115.     }
  116.     // Back up to next bit
  117.     if (--bit < 0)
  118.     {
  119.       bit = 7;
  120. #ifdef MSB_FIRST
  121.       ip++;
  122.       jp++;
  123. #else
  124.       ip--;
  125.       jp--;
  126. #endif
  127.     } // if --bit
  128.  
  129.   } // for nq
  130.  
  131. } // QuadCode::QuadCode
  132.  
  133. ///////////////////////////////////////////////////////
  134. // QuadCode::Init: QuadCode initializer from string.
  135.  
  136. void QuadCode::Init (const char *chqc)
  137. // chqc         is the quadcode in a null-terminated
  138. //              character representation - i.e., "123"
  139. {
  140.   int nq = strlen (chqc);
  141. #ifndef STAT_QC
  142.   qca = NULL;
  143. #endif
  144.   nquits = 0;
  145.   assert (nq > 0 && nq <= MAXQUITS);
  146.   size_t nbytes = QC_NBYTES (nq);
  147. #ifndef STAT_QC
  148.   qca = new BYTE [nbytes];
  149.   assert (qca != NULL);
  150. #endif
  151.   memset (qca, '\0', nbytes);
  152.  
  153.   // Store quadcode in binary form, from msq to lsq.
  154.   int  i;
  155.   int  pos; // pos within byte of this quit (0,1,2,3)
  156.   BYTE *p;  // ptr to current byte in qc
  157.   for (i = 0, pos = 0, p = qca; i < nq; i++)
  158.   {
  159.     int val = chqc[i] - '0';
  160.     assert (val >= 0 && val <= 3);
  161.     *p |= val << QCshifts[pos];
  162.     if (++pos > 3)
  163.     {
  164.       pos = 0;
  165.       p++;
  166.     }
  167.   } // for i
  168.  
  169.   nquits = nq;
  170. } // QuadCode::Init
  171.  
  172. ///////////////////////////////////////////////////////
  173. // QuadCode::GetQuit: Return single quit from quadcode.
  174.  
  175. int QuadCode::GetQuit (int quit)
  176. // quit is the pos# of the quit to extract (zero-based).
  177. //      Pos 0 is the high-order quit ('1' in "123").
  178. {
  179.   assert (quit <= nquits && quit >= 0);
  180.  
  181.   int byte = quit / 4;
  182.   int pos = quit % 4;
  183.   return ( (*(qca + byte) & QCmasks[pos]) >>
  184.       QCshifts[pos]);
  185. } // QuadCode::GetQuit
  186.  
  187. ///////////////////////////////////////////////////////
  188. // QuadCode::SetQuit: Set value of a single quit.
  189.  
  190. void QuadCode::SetQuit (int quit, int val)
  191. // quit is the pos# of the quit to extract (zero-based).
  192. // val  is the value of the quit (0, 1, 2 or 3).
  193. {
  194.   assert (quit <= nquits && quit >= 0 && val >= 0 &&
  195.       val < 4);
  196.  
  197.   BYTE *p = qca + quit / 4;
  198.   int pos = quit % 4;
  199.   // Clear out the old value
  200.   *p &= (255 - QCmasks[pos]);
  201.   // Put in the new value
  202.   *p |= val << QCshifts[pos];
  203. } // QuadCode::SetQuit
  204.  
  205. ///////////////////////////////////////////////////////
  206. // QuadCode::ToIJ: Convert the quadcode value to (I,J).
  207. // The offsets returned are the coords of the
  208. // upper-left corner of the quadcode.
  209.  
  210. void QuadCode::ToIJ (COORD &i, COORD &j, int &nq)
  211. // i      is the row#
  212. // j      is the col#
  213. // nq     is the #quits
  214. {
  215.   i = j = nq = 0;
  216.   if (nquits < 1)
  217.     return;
  218.   assert (nquits <= MAXQUITS);
  219.   nq = nquits;
  220.  
  221.   // Go from lsq to msq.  Following loop is based on the
  222.   // conversion algorithm by Gargantini:
  223. #ifdef MSB_FIRST
  224.   BYTE *ip = (BYTE *)&i + sizeof(COORD) - 1;
  225.   BYTE *jp = (BYTE *)&j + sizeof(COORD) - 1;
  226. #else
  227.   BYTE *ip = (BYTE *)&i;
  228.   BYTE *jp = (BYTE *)&j;
  229. #endif
  230.   int   quit,       // current quit# in qc
  231.         bit = 0;    // current bit# in byte of (i,j)
  232.  
  233.   for (quit = nquits-1; quit >= 0; quit--)
  234.   {
  235.     int val = GetQuit (quit);
  236.     // Bit pos 0 gives J val, bit pos 1 gives I val.
  237.     int ival = val >> 1;
  238.     int jval = val & 1;
  239.     *ip |= (ival << bit);
  240.     *jp |= (jval << bit);
  241.     // Advance to next bit
  242.     if (bit == 7)
  243.     {
  244.       bit = 0;
  245. #ifdef MSB_FIRST
  246.       ip--;
  247.       jp--;
  248. #else
  249.       ip++;
  250.       jp++;
  251. #endif
  252.     }
  253.     else
  254.       bit++;
  255.   } // for quit
  256.  
  257. } // QuadCode::ToIJ
  258.  
  259. ///////////////////////////////////////////////////////
  260. // QuadCode::Compare: Compare one quadcode to another.
  261. // Return 0 if the two quadcodes are equal; -1 if the
  262. // current quadcode is less than qc; or +1 if the
  263. // current quadcode is greater than qc.
  264.  
  265. int QuadCode::Compare (QuadCode &qc)
  266. // qc         is the quadcode to compare to
  267. {
  268.   // Check for zero-length quadcodes
  269.   if (nquits == 0)
  270.   {
  271.     if (qc.nquits == 0)
  272.       return 0;
  273.     else
  274.       return -1;
  275.   }
  276.   else if (qc.nquits == 0)
  277.     return 1;
  278.  
  279.   BYTE *p1 = qca;
  280.   BYTE *p2 = qc.qca;
  281.   BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
  282.   BYTE *end2 = p2 + QC_NBYTES (qc.nquits) - 1;
  283.  
  284.   // Compare each byte of the two quadcodes.
  285.   for ( ; p1 <= end1 && p2 <= end2; p1++, p2++)
  286.     if (*p1 != *p2)
  287.     {
  288.       if (*p1 < *p2)
  289.         return -1;
  290.       else
  291.         return 1;
  292.     }
  293.  
  294.   if (nquits == qc.nquits)
  295.     // quadcodes same
  296.     return 0;
  297.   else if (nquits < qc.nquits)
  298.     // this quadcode contains qc
  299.     return -1;
  300.   else
  301.     // qc contains this quadcode
  302.     return 1;
  303. } // QuadCode::Compare
  304.  
  305. ///////////////////////////////////////////////////////
  306. // QuadCode::Sibling: Compare one quadcode to another.
  307. // Return TRUE if they are siblings, FALSE if not.
  308.  
  309. int QuadCode::Sibling (QuadCode *qc)
  310. // qc         is the quadcode to compare to
  311. {
  312.   // Must be the same length, can't be empty.
  313.   if (qc == NULL || nquits != qc->nquits || nquits==0)
  314.     return (FALSE);
  315.  
  316.   BYTE *p1 = qca;
  317.   BYTE *p2 = qc->qca;
  318.   BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
  319.  
  320.   // Compare each byte of the two quadcodes.
  321.   // If any differ except the last, then not siblings.
  322.   for ( ; p1 < end1; p1++, p2++)
  323.     if (*p1 != *p2)
  324.       return (FALSE);
  325.  
  326.   if (*p1 == *p2)
  327.     // Quadcodes are same
  328.     return (FALSE);
  329.  
  330.   // Make sure final byte matches in all but last quit.
  331.   int pos = (nquits-1) % 4;
  332.   return
  333.       ((*p1 & QCimasks[pos]) == (*p2 & QCimasks[pos]));
  334.  
  335. } // QuadCode::Sibling
  336.  
  337. ///////////////////////////////////////////////////////
  338. // QuadCode::Contains: Compare one quadcode to another.
  339. // Return TRUE if the current quadcode contains qc
  340. // (i.e., is equal to it or is a parent of it), or
  341. // FALSE otherwise.
  342.  
  343. int QuadCode::Contains (QuadCode &qc)
  344. // qc         is the quadcode to compare to
  345. {
  346.   if (nquits > qc.nquits)
  347.     return (FALSE);
  348.   if (nquits == 0)
  349.     return (TRUE);
  350.  
  351.   BYTE *p1 = qca;
  352.   BYTE *p2 = qc.qca;
  353.   BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
  354.   BYTE *end2 = p2 + QC_NBYTES (qc.nquits) - 1;
  355.  
  356.   // Compare each byte of the two quadcodes.
  357.   for ( ; p1 <= end1 && p2 <= end2; p1++, p2++)
  358.     if (*p1 != *p2)
  359.     {
  360.       // Found a byte that differs.  This quadcode
  361.       // contains qc iff: (1) We are at the last byte
  362.       // of this quadcode; and  (2) All quits in this
  363.       // quadcode before the last one match the
  364.       // corresponding quits in qc.
  365.       if (p1 != end1)
  366.         return (FALSE);
  367.       int lastpos = (nquits - 1) % 4;
  368.       int pos;
  369.       for (pos = lastpos; pos >= 0; pos--)
  370.         if ((*p1 & QCmasks[pos]) !=
  371.             (*p2 & QCmasks[pos]))
  372.           return (FALSE);
  373.       // They match up to nquits.
  374.       return (TRUE);
  375.     }
  376.  
  377.   // All bytes match - either qc's are same or this is
  378.   // the parent.
  379.   return (TRUE);
  380. } // QuadCode::Contains
  381.  
  382. ///////////////////////////////////////////////////////
  383. // QuadCode::MakeParent: Make quadcode into its parent
  384.  
  385. void QuadCode::MakeParent (void)
  386. {
  387.   // Clear the bits that saved the last quit.  We do
  388.   // not bother to reclaim storage if the size of the
  389.   // quadcode is reduced.
  390.   nquits--;
  391.   int byte = nquits / 4;
  392.   int pos = nquits % 4;
  393.   *(qca + byte) &= QCimasks[pos];
  394. } // QuadCode::MakeParent
  395.  
  396. ///////////////////////////////////////////////////////
  397. // QuadCode::operator=: Assign one quadcode the same
  398. // value as another.  Note that the target quadcode is
  399. // assumed to be initialized already.
  400.  
  401. QuadCode &QuadCode::operator= (QuadCode &qc)
  402. // qc         is the quadcode to copy
  403. {
  404. #ifdef STAT_QC
  405.   memcpy (qca, qc.qca, NBYTE_QC);
  406. #else
  407.   FreeMem();
  408.  
  409.   size_t nbytes = QC_NBYTES (qc.nquits);
  410.   qca = new BYTE [nbytes];
  411.   assert (qca != NULL);
  412.   memcpy (qca, qc.qca, nbytes);
  413. #endif  // STAT_QC
  414.  
  415.   nquits = qc.nquits;
  416.   return (*this);
  417. } // QuadCode::operator=
  418.  
  419. ///////////////////////////////////////////////////////
  420. // operator<<: Overload the "Put to" operator for
  421. // QuadCode output to stream.
  422.  
  423. ostream &operator<< (ostream &stream, QuadCode &qc)
  424. // stream     is the stream to print to
  425. // qc         is the quadcode to print
  426. {
  427.   int   quit;
  428.  
  429.   for (quit = 0; quit < qc.nquits; quit++)
  430.     stream << (char)(qc.GetQuit (quit) + '0');
  431.   return (stream);
  432. } // operator<<
  433.  
  434. ///////////////////////////////////////////////////////
  435. // operator>>: Overload the "Get From" operator for
  436. // QuadCode input from stream.
  437.  
  438. istream &operator>> (istream &stream, QuadCode &qc)
  439. // stream     is the stream to get from
  440. // qc         is the quadcode to store the result in
  441. {
  442.   char  tmp[80];
  443.  
  444.   qc.FreeMem();
  445.   stream >> tmp;
  446.   qc.Init (tmp);
  447.   return (stream);
  448. } // operator>>
  449.